#include <bits/stdc++.h>
using namespace std;

/*
3446. 按对角线进行矩阵排序
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
右上角三角形 的对角线按 非递减顺序 排序。
 

示例 1：

输入： grid = [[1,7,3],[9,8,2],[4,5,6]]

输出： [[8,2,3],[9,6,7],[4,5,1]]

解释：



标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：

[1, 8, 6] 变为 [8, 6, 1]。
[9, 5] 和 [4] 保持不变。
标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：

[7, 2] 变为 [2, 7]。
[3] 保持不变。
示例 2：

输入： grid = [[0,1],[1,2]]

输出： [[2,1],[1,0]]

解释：



标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。

示例 3：

输入： grid = [[1]]

输出： [[1]]

解释：

只有一个元素的对角线已经符合要求，因此无需修改。

 

提示：

grid.length == grid[i].length == n
1 <= n <= 10
-105 <= grid[i][j] <= 105
*/

// 法一
class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        // 左下角三角形 主对角线 k >= 0 非递增排序
        for (int k = 0; k < n; k++) {
            vector<int> diag;
            // 对角线遍历收集
            for (int j = 0; j < n - k; j++) {
                int i= j  +k;
                diag.push_back(grid[i][j]);
            }
            //
            sort(diag.rbegin(), diag.rend());
            // 将排序后的元素放回原位置
            for (int j = 0; j < n - k; ++j) {
                int i = j + k;
                grid[i][j] = diag[j];
            }
        }
        // 右上角的
        for (int k = -1; k >= -(n - 1); --k) {
            int m = -k; // m为正数，代表偏移量
            vector<int> diag;
            // 收集对角线上的元素
            for (int i = 0; i < n - m; ++i) {
                int j = i + m;
                diag.push_back(grid[i][j]);
            }
            // 非递减排序
            sort(diag.begin(), diag.end());
            // 将排序后的元素放回原位置
            for (int i = 0; i < n - m; ++i) {
                int j = i + m;
                grid[i][j] = diag[i];
            }
        }
        return grid;
    }
};

// 法二
// 临时数组的临时存储 栈上的速度更快
class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> tmp(n, 0); // 临时数组，用于存储对角线元素并排序

        // 左下三角形（包括主对角线）的对角线  按非递增排序
        for (int i = 0; i < n; i++) {
            // 收集当前对角线上的所有元素
            // 对角线起点为(i, 0)，元素坐标为(i+j,
            // j)，其中j从0开始，确保不越界（i+j < n）
            for (int j = 0; i + j < n; j++)
                tmp[j] = grid[i + j][j];

            // 排序范围：从tmp起始到有效元素个数（n - i）
            sort(tmp.begin(), tmp.begin() + n - i,
                 [](int a, int b) { return a > b; });

            // 排序后放回原来位置
            for (int j = 0; i + j < n; j++) {
                grid[i + j][j] = tmp[j];
            }
        }

        // 右上角 与之类似处理
        // 这些对角线满足 列索引 - 行索引 = i（i >= 1），即行索引 - 列索引 =
        // -i（<0），需按非递减排序
        for (int i = 1; i < n; i++) {
            // 收集当前对角线上的所有元素
            // 对角线起点为(0, i)，元素坐标为(j,
            // i+j)，其中j从0开始，确保不越界（i+j < n）
            for (int j = 0; i + j < n; j++) {
                tmp[j] = grid[j][i + j];
            }

            // 对收集的对角线元素进行非递减排序（从小到大）
            // 排序范围：从tmp起始到有效元素个数（n - i）
            sort(tmp.begin(), tmp.begin() + n - i);

            // 将排序后的元素放回原对角线位置
            for (int j = 0; i + j < n; j++) {
                grid[j][i + j] = tmp[j];
            }
        }
        return  grid;
    }
};

// 法三
class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();  // m为行数，n为列数（题目中为n×n矩阵，此处通用化处理）
        
        // 核心思路：用k统一标识所有对角线，k = i - j + n（偏移n避免负索引）
        // 对角线特征：同一对角线上的元素满足i - j为常数，k值相同
        // k的范围：1到m+n-1（覆盖所有可能的对角线）
        for (int k = 1; k < m + n; k++) {
            // 计算当前对角线中列索引j的最小值和最大值（确保i和j均在有效范围内）
            // min_j：j的下限。当i=0时，j = n - k，若为负数则取0（避免j越界）
            int min_j = max(n - k, 0);
            // max_j：j的上限。当i=m-1时，j = m + n - 1 - k，若超过n-1则取n-1（避免j越界）
            int max_j = min(m + n - 1 - k, n - 1);
            
            vector<int> a;  // 存储当前对角线上的所有元素
            // 收集对角线上的元素：i由k和j推导（k = i - j + n → i = k + j - n）
            for (int j = min_j; j <= max_j; j++) {
                a.push_back(grid[k + j - n][j]);
            }
            
            // 判断对角线位置并排序：
            // 1. 若min_j > 0：对角线属于右上三角形（j起始位置在左边界右侧），按非递减排序
            // 2. 若min_j = 0：对角线属于左下三角形或主对角线（j从左边界开始），按非递增排序
            if (min_j > 0) { 
                ranges::sort(a);  // 非递减排序（从小到大）
            } else { 
                ranges::sort(a, greater<int>());  // 非递增排序（从大到小）
            }
            
            // 将排序后的元素放回原对角线位置
            for (int j = min_j; j <= max_j; j++) {
                grid[k + j - n][j] = a[j - min_j];  // a的索引对应j与min_j的偏移量
            }
        }
        return grid;
    }
};